package JZ_Offer.dataStructure.tree;

import base.TreeLinkNode;

import java.util.ArrayList;

/**
 * 二叉树的下一个结点
 *
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 */
public class JZ8_二叉树的下一个结点 {

    private static ArrayList<TreeLinkNode> list = new ArrayList<>();

    private static TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 找到根节点
        TreeLinkNode root = pNode;
        while (root.next != null) {
            root = root.next;
        }

        // 中序遍历
        InOrder(root);

        // 找到下一个节点
        for (int i = 0; i < list.size(); i++) {
            if (pNode == list.get(i)) {
                return i == list.size() - 1 ? null : list.get(i + 1);
            }
        }

        return null;
    }

    // 中序遍历
    private static void InOrder(TreeLinkNode root) {
        if (root != null) {
            InOrder(root.left);
            list.add(root);
            InOrder(root.right);
        }
    }

    /**
     *       a
     *   b       c
     * d  e    f  g
     *   h i
     * 仔细观察，可以把中序下一结点归为几种类型：
     * 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
     * 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
     * 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
     * 如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
     */
    private static TreeLinkNode GetNext1(TreeLinkNode pNode) {
        // 有右子树 下一节点是右子树的最左节点
        if (pNode.right != null) {
            TreeLinkNode left = pNode.right;
            while (left.left != null) {
                left = left.left;
            }
            return left;
        }

        // 没有右子树
        // 父节点的左节点
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }

        // 父节点的右节点
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;
            while (pNext.next != null && pNext.next.left != pNext) {
                pNext = pNext.next;
            }
            return pNext.next;
        }

        return null;
    }

}
